#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cassert>

#include "gtest/gtest.h"

static const int N = 100;

// This homemade class implements the more or less efficient 
// string in terms of copying.
class String {
 public:
  // "explicit" disables any implicit cast making sure 
  // which constructor exactly is being called.
  explicit String(const std::string& value) { 
    init(value.c_str(), value.length()); 
  }
  String(const String& value) { init(value.data_, value.sz_); }
  ~String() { free(data_); }

  // Perhaps this method is only one attempt to use memory allocation
  // efficiently.
  String& operator=(const String& value) {
    if (this != &value) {
      // Memory is re-allocated only if a source is longer the current
      // string. It is clear that this implementation will only increase 
      // memory allocated by the string.
      if (value.sz_ > sz_) data_ = (char*)std::realloc(data_, value.sz_);
      sz_ = value.sz_;
      std::memcpy(data_, value.data_, sz_);
    }
    return *this;
  }

  friend class StringCmp;
  friend class StringPointerCmp;

 private:
  void init(const char* data, size_t sz) {
    sz_ = sz;
    data_ = (char*)malloc(sz_);
    std::memcpy(data_, data, sz_);
  }
  char* data_;
  size_t sz_;
};

std::vector<std::string> std_strings;
std::vector<std::string*> std_strings_p;
std::vector<String> strings;
std::vector<String*> strings_p;

// Functor to compare two std::string.
class StlStringCmp {
 public:
  bool operator()(const std::string& a, const std::string& b) {
    return a < b;
  }
};

TEST(SortingStlString, StlString) {
  std::sort(std_strings.begin(), std_strings.end(), StlStringCmp());
}

// Functor to compare two std::string*.
class StlStringPointerCmp {
 public:
  bool operator()(const std::string* a, const std::string* b) {
    return *a < *b;
  }
};

TEST(SortingStlString, StlStringPointer) {
  std::sort(std_strings_p.begin(), std_strings_p.end(), StlStringPointerCmp());
}

// Functor to compare two String.
class StringCmp {
 public:
  bool operator()(const String& a, const String& b) {
    assert(a.sz_ == b.sz_);
    return std::memcmp(a.data_, b.data_, a.sz_);
  }
};

TEST(SortingStlString, String) {
  std::sort(strings.begin(), strings.end(), StringCmp());
}

// Functor to compare two String*.
class StringPointerCmp {
 public:
  bool operator()(const String* a, const String* b) {
    assert(a->sz_ == b->sz_);
    return std::memcmp(a->data_, b->data_, a->sz_);
  }
};

TEST(SortingStlString, StringPointer) {
  std::sort(strings_p.begin(), strings_p.end(), StringPointerCmp());
}

int main(int argc, char* argv[]) {
  // The filler to make strings long enough making their copying expensive.
  std::string big(1024 * 1024, '?');
  for (int i = 0; i < N; ++i) {
    // All strings are the same length. The comparison functions rely on it.
    std::stringstream fmt;
    fmt << N * 2 - i << big;
    std_strings.push_back(fmt.str());
    std_strings_p.push_back(new std::string(fmt.str()));
    strings.push_back(String(fmt.str()));
    strings_p.push_back(new String(fmt.str()));
  }

  testing::InitGoogleTest(&argc, argv);
  // Enforce to print out tests' timing.
  testing::GTEST_FLAG(print_time) = true;
  return RUN_ALL_TESTS();
}
